//Implement pow(x, n), which calculates x raised to the power n (i.e., xn). 
//
// 
// Example 1: 
//
// 
//Input: x = 2.00000, n = 10
//Output: 1024.00000
// 
//
// Example 2: 
//
// 
//Input: x = 2.10000, n = 3
//Output: 9.26100
// 
//
// Example 3: 
//
// 
//Input: x = 2.00000, n = -2
//Output: 0.25000
//Explanation: 2-2 = 1/22 = 1/4 = 0.25
// 
//
// 
// Constraints: 
//
// 
// -100.0 < x < 100.0 
// -231 <= n <= 231-1 
// -104 <= xn <= 104 
// 
// Related Topics 数学 二分查找 
// 👍 646 👎 0


package leetcode.editor.cn;

import org.junit.Assert;

//Java：Pow(x, n)
class P50PowxN {
    public static void main(String[] args) {
        Solution solution = new P50PowxN().new Solution();
        // TO TEST
        double a = 0.54189;
        int b = 5;
        System.out.println(Math.pow(a, b));
        System.out.println(solution.myPow(a, b));
        Assert.assertEquals(solution.myPow(a, b),Math.pow(a, b), 11);

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double myPow(double x, int n) {
            double res = 1.0;
            for(int i = n; i != 0; i /= 2){
                if(i % 2 != 0){
                    res *= x;
                }
                x *= x;
            }
            return  n < 0 ? 1 / res : res;
        }
        public double myPow1(double x, int n) {
            if (n == 0) {
                return 1;
            }
            if (n == 1) {
                return x;
            }
            String s = String.valueOf(x);
            int index = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '.') {
                    index = i;

                }
            }
            int decimal = (s.length() - index) * n;
            if (decimal > 16 && x < 1) {
                return 0.0;
            }
            double res = myPowAbc(x, Math.abs(n));
            if (n < 0) {
                return 1 / res;
            }
            return res;
        }

        double myPowAbc(double x, int n) {
            if (n == 2) {
                return x * x;
            }
            if (n == 1) {
                return x;
            }
            if (n == 0) {
                return 1;
            }
            if (n % 2 == 0) {
                return myPowAbc(x, n / 2) * myPowAbc(x, n / 2);
            } else {
                return myPowAbc(x, n / 2) * myPowAbc(x, n / 2) * x;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}